package com.tgy.查找;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/***
 * @ClassName: FibonacciSearch
 * @Description: 斐波那契查找 这个也是需要数组是有序的才能执行查找
 * @Auther: tanggy3
 * @Date: 17:27 2022/8/31
 * @version : V1.0
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] ints = {3, 2, 5,1,4,8};
        List<Integer> integers = Arrays.stream(ints).boxed().toList();
        System.out.println(integers.contains(6 - 2));
        //System.out.println(Arrays.toString(fib(30)));
        System.out.println(fibSearch(ints,1));

//        int[] ints1 = Arrays.copyOf(ints, 5);
//        System.out.println(Arrays.toString(ints1));
    }

    static int[] fib(int maxSize) {
        int[] ints = new int[maxSize];
        ints[0] = 1;
        ints[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            ints[i] = ints[i - 1] + ints[i - 2];
        }
        return ints;
    }


    //编写斐波那契查找算法
    //使用非递归的方式编写算法

    /**
     * @param a   数组
     * @param key 我们需要查找的关键码(值)
     * @return 返回对应的下标，如果没有-1
     */
    public static int fibSearch(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        int k = 0; //表示斐波那契分割数值的下标
        int mid = 0; //存放mid值
        int f[] = fib(20); //获取到斐波那契数列
        //获取到斐波那契分割数值的下标
        while (high > f[k] - 1) {
            k++;
        }
        /**
         * 找到合适的k
         * 因为 f[k] 值 可能大于 a 的 长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[]
         * 不足的部分会使用0填充
         *
         * 实际上需求使用a数组最后的数填充 temp
         * temp = {1,8, 10, 89, 1000, 1234, 0, 0}  => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
         * 填充后面的大数
         */
        int[] temp = Arrays.copyOf(a, f[k]);//temp数组的大小和斐波那契的值一致的
        for(int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }
        // 使用while来循环处理，找到我们的数 key
        while (low <= high) { // 只要这个条件满足，就可以找

            mid = low + f[k - 1] - 1;
            if(key < temp[mid]) {//在左侧
                high = mid - 1;
                /**
                 * 为什么是 k--
                 * 说明
                 * 1. 全部元素 = 前面的元素 + 后边元素
                 * 2. f[k] = f[k-1] + f[k-2]
                 * 因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
                 * 即 在 f[k-1] 的前面继续查找 k--
                 * 即下次循环 mid = f[k-1-1]-1
                 */
                k--;
            }else if ( key > temp[mid]) {//在右侧
                low = mid+1;
                /**
                 * 为什么是k -=2 结合图看能理解，它本来就在-2的那一段里，现在还需要向在缩小一段
                 * 说明
                 * 1. 全部元素 = 前面的元素 + 后边元素
                 * 2. f[k] = f[k-1] + f[k-2]
                 * 3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-2] = f[k-3] + f[k-4]
                 * 4. 即在f[k-2] 的前面进行查找 k -=2
                 * 5. 即下次循环 mid = f[k - 1 - 2] - 1
                 */
                k -= 2;
            }else {//找到
                //需要确定，返回的是哪个下标
                if(mid <= high) {
                    return mid;
                } else {
                    return high; //因为数组是补长过的，所以后面可能会有几个一样的大的在high后面
                }
            }
        }
        return -1;
    }


    static List<Integer> seqSearch(int[] arr, int num) {
        ArrayList<Integer> ints = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                ints.add(i + 1);
            }
        }
        return ints;
    }
}
